/*
 * @lc app=leetcode id=497 lang=cpp
 *
 * [497] Random Point in Non-overlapping Rectangles
 */

// @lc code=start
class Solution {
public:
    Solution(vector<vector<int>>& rects) {
        rects_ = rects;
        int num = 0;
        select.push_back(0);
        for(auto rect : rects_) {
            int temp = (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
            num += temp;
            select.push_back(num);
        }
    }
    
    vector<int> pick() {
        int t = rand() % select.back();
        int idx = 0;
        for (int i = 0; i < select.size(); ++i) {
            if (t >= select[i] && t < select[i+1]) {
                idx = i;
                break;
            }
        }
        auto rect = rects_[idx];        
        return {rand() % (rect[2] - rect[0] + 1) + rect[0], rand() % (rect[3] - rect[1] + 1) + rect[1]};

        
    }
    vector<vector<int>> rects_;
            vector<int> select;


};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(rects);
 * vector<int> param_1 = obj->pick();
 */
// @lc code=end

